package com.leetcode;


/**
 * 1144. 递减元素使数组呈锯齿状 (中等)
 * 给你一个整数数组nums，每次 操作会从中选择一个元素并 将该元素的值减少1。
 * 如果符合下列情况之一，则数组A就是 锯齿数组：
 * 每个偶数索引对应的元素都大于相邻的元素，即A[0] > A[1] < A[2] > A[3] < A[4] > ...
 * 或者，每个奇数索引对应的元素都大于相邻的元素，即A[0] < A[1] > A[2] < A[3] > A[4] < ...
 * 返回将数组nums转换为锯齿数组所需的最小操作次数。
 */
public class LeetCode1144 {

    public static void main(String[] arg0) {
        int[] test = new int[]{2, 7, 10, 9, 8, 9};
        System.out.println("将数组nums转换为锯齿数组所需的最小操作次数 = " + movesToMakeZigzag(test));
    }

    /**
     * a,b分别记录偶数下标为峰和奇数下标为峰的情况需要递减的次数
     * 最后去a,b中小的作为答案
     */
    public static int movesToMakeZigzag(int[] nums) {
        int a = 0, b = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) { // 这里记录偶数为峰的情况
                if ((i + 2) < nums.length) {
                    a += Math.max(nums[i + 1] - Math.min(nums[i], nums[i + 2]) + 1, 0);
                } else if ((i + 1) < nums.length) { // i + 1 = nums.length - 1 的情况
                    a += Math.max(nums[i + 1] - nums[i] + 1, 0);
                }
            } else { // 这里记录奇数为峰的情况
                if (i == 1) { // 首次先做一个将 nums[0] 降低的调整
                    b += Math.max(nums[i - 1] - nums[i] + 1, 0);
                }
                if ((i + 2) < nums.length) {
                    b += Math.max(nums[i + 1] - Math.min(nums[i], nums[i + 2]) + 1, 0);
                } else if ((i + 1) < nums.length) { // i + 1 = nums.length - 1 的情况
                    b += Math.max(nums[i + 1] - nums[i] + 1, 0);
                }
            }
        }
        return Math.min(a, b);
    }

}
